/* Delta Debugging tool for C code
   Collin Engstrom and Jacob Burnim,
   ParLab
   2009 */
#include <iostream>
#include <cstdlib>
#include <fstream>
#include <cmath>
#include <vector>
#include <string>
#include <cassert>

using namespace std;

// Path to cilly driver.
#define cillyDriver "/home/jburnim/ksen_repo/projects/cil/bin/cilly"

//Global path varibale for prog location:
char *path ;

void vecInit(vector<int>& list, int count)
{
  for (int i = 1; i <= count ; i++)
    {
      list.push_back(i);
    }
}

void output( vector<int> list )
{
  cout << "{";
  for(int i = 0; i < list.size(); i++)
    {
      cout << list[i] << ",";
    }
  cout << "}" << endl;
}

void outputLists( vector < vector <int> > lists)
{
  cout << "{";
  for(int i = 0; i < lists.size(); i++)
    {
      cout << "{ " ;
      for(int j = 0; j< lists[i].size(); j++)
        {
          cout << lists[i][j] << ",";
        }
      cout << " }" ;

    }
  cout << "}" << endl;
}

vector< vector <int> > split(vector<int> superList, int numLists)
{
  vector < vector<int> > external;
  vector<int> internal;
  const int superSize = superList.size();
  int start = 0;

  for(int i = 0; i < numLists; i++)
    {
      int size = int(    ceil ((superSize - start) / float(numLists - i)  ) );
      internal.clear();
      for(int j = start; j < (start + size); j++)
        {
          internal.push_back(superList.at(j));
        }
      external.push_back(internal);
      start += internal.size();
    }

  assert(external.size() == numLists);

  for(int i = 0; i < external.size(); i++)
    {
      assert(external[i].size() > 0);
    }

  return external;
}

bool isEqual(vector <int> list1, vector <int> list2)
{
  bool flag = false;

  if(list1.size() == list2.size())
    {
      flag = true;
      for(int i = 0; i < list1.size(); i++)
        {
          if (list1.at(i) != list2.at(i))
            {
              flag = false;
              break;
            }
        }
    }

  return flag;
}

vector < vector <int> > setComplement(vector < vector <int> > list, vector <int> list2)
{

  for(int i = 0; i < list.size(); i++)
    {
      if  (isEqual(list[i],list2))
        {
          list.erase(list.begin() + i);
        }
    }
  return list;
}

vector <int> setUnion(vector < vector <int> > lists)
{
  vector <int> listU;
  for(int i = 0; i < lists.size(); i++)
    {
      for(int j = 0; j < lists[i].size(); j++)
        {
          listU.push_back(lists[i][j]);
        }
    }
  return listU;
}

/*
  test:
  Eventually this function will take a list and
  return true if there is a failure or false
  if the failure disappeared. It will use the
  delta.dat file to communicate with the CIL
  module.
*/
/*bool test(vector <int> list)
  {
  bool containsA = false;
  bool containsB = false;

  for (int i = 0; i < list.size(); i++)
  {
  if(list.at(i)==2)
  {
  containsA=true;
  break;
  }
  }


  for(int i = 0; i < list.size(); i++)
  {
  if(list.at(i)==9999)
  {
  containsB=true;
  break;
  }
  }

  return !(containsA&&containsB); //Want failure if nine is present
  }*/

bool test(vector <int> list)
{
  int result = 0;
  ofstream outfile;
  ifstream infile;

  //Make string for argument
  string paths = path;
  string program = (string)cillyDriver + " --dofloatddInstrument --verbose --save-temps -lm " + paths;

  //Open output file and print list of changes
  //outfile.open("../../cil-1.3.7/src/ext/changefile.dat");
  outfile.open("changefile.dat");

  assert(outfile.is_open());

  for(int i = 0; i < list.size(); i++)
    {
      outfile << list.at(i) << endl;
    }
  outfile.close();

  //Run CIL module and then program with modifcations
  system(program.c_str());
  result = system("./a.out");

  /*//Get status of program run
    infile.open("result.dat");
    assert(infile.is_open());
    infile >> status;
    infile.close();*/

  return ((result == 0) ? 0 : 1);
}

vector <int> delta(vector <int> list, int sublists)
{
  bool isFail = 0;
  int n = sublists;
  bool incGran = true;
  const int count = list.size();
  vector < vector <int> > lists;
  static vector <int> lastFail ;
  vector < vector <int> > comp;

  cout << "count: " << count << endl;
  cout << "n: " << n << endl;

  if(n > count)
    {
      incGran = false;
      n = count;
    }

  if(count == 1)
    {
      return list;
    }

  lists = split(list, n);
  cout << "Lists after splitting: ";
  outputLists(lists);

  for (int j = 0; j < lists.size(); j++)
    {
      if(test(lists[j]) == false)
        {
          cout << "Failure found in list: " << j <<endl;
          isFail = 1;
          lastFail = lists[j];
          list = delta(lists[j], n);
          break;
        }
    }

  if (isFail == 0)
    {
      cout << "No failure found in original. Checking complements..." << endl;
      cout << "n: " << n << endl;
      for (int j = 0; j < lists.size(); j++)
        {
          cout << "Complement " << j << endl;
          comp = setComplement(lists,lists[j]);
          outputLists(comp);

          if (test(setUnion(comp)) == 0)
            {
              isFail = 1;
              lastFail = setUnion(comp);
              list = delta(setUnion(comp), n);

              break;
            }

        }
    }

  if (isFail == 0)
    {
      cout << "No failure found. Increasing granularity...\n" ;
      cout << "list: " ;
      output(list) ;
      cout << "lastFail: " ;
      output(lastFail) ;

      //If we're already at max granularity
      if(incGran == false)
        {
          return lastFail;
        }

      list = delta(list, 2*n);
    }

  return list;
}

int main(int argc, char *argv[])
{
  //Number of potential promotions
  int count;

  //Set path variable:
  assert(path = argv[1]);

  //Make string for argument
  string paths = path;
  string cilMachine = "CIL_MACHINE=\"short=2,2 int=4,4 long=4,4 long_long=8,4 pointer=4,4 enum=4,4 float=4,4 double=8,4 long_double=12,4 void=1 bool=1,1 fun=1,1 alignof_string=1 max_alignment=16 size_t=unsigned_int wchar_t=int char_signed=true const_string_literals=true big_endian=false __thread_is_keyword=true __builtin_va_list=true underscore_name=false\" ";
  string program = cilMachine + (string)cillyDriver +" --dofloatddInstrument --verbose --save-temps -lm --envmachine " + paths;

  //Open floatCount.dat to obtain number of floats
  assert(system(program.c_str())==0);

  //Open floatCount.dat to obtain number of floats
  ifstream infile;
  infile.open("floatCount.dat");

  //Check to see that input file is open and read in counter
  assert(infile.is_open());
  infile >> count;
  infile.close();

  //Declare a vector of integers and populate based on counter
  vector<int> list;
  vecInit(list, count);
  cout << "Original list: " ;
  output(list);

  assert(test(list) == 0);

  //Invoke delta debugging algorithm on vector.
  vector<int> listFail = delta(list,2);
  output(listFail);

  return EXIT_SUCCESS;
}
